忍者算法

Appearance

路径总和 III：二叉树中的忍者追踪术 ​

现实映射：宝藏地图的密码破解 ​

考古学家发现了一张古老的宝藏地图，地图上标注了一棵神秘的二叉树，每个节点都藏有一个数字密码。为了找到宝藏，我们需要计算从任意节点出发，向下追踪路径，使得路径上的数字之和恰好等于目标值的所有可能路径。

这正是我们今天要解决的算法难题——路径总和 III！

路径总和示意图

问题描述 ​

LeetCode第437题要求：给定一个二叉树的根节点 root 和一个整数 targetSum，返回该二叉树中路径和等于 targetSum 的路径数目。路径不需要从根节点开始，也不需要在叶子节点结束，但必须是从父节点到子节点的方向。

示例：

输入：
root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8

输出：3

解释：
路径1：5 → 3
路径2：5 → 2 → 1
路径3：-3 → 11

直觉解法：双重递归 ​

就像考古学家需要逐层挖掘和逐点分析，我们可以用双重递归的策略来解决这个问题：

  1. 外层递归：遍历每个节点，作为路径的起点
  2. 内层递归：从当前节点出发，向下搜索所有可能的路径，并计算路径和

Java实现 ​

java
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        
        // 从当前节点开始的路径数 + 左子树的路径数 + 右子树的路径数
        return countPath(root, targetSum) 
             + pathSum(root.left, targetSum) 
             + pathSum(root.right, targetSum);
    }

    private int countPath(TreeNode node, long targetSum) {
        if (node == null) return 0;

        int count = 0;
        if (node.val == targetSum) {
            count++;
        }

        // 递归计算左右子树
        count += countPath(node.left, targetSum - node.val);
        count += countPath(node.right, targetSum - node.val);
        return count;
    }
}

复杂度分析
时间复杂度：O(n²)（每个节点作为起点，最坏情况下需要遍历整棵树）
空间复杂度：O(n)（递归栈深度）

忍者解法：前缀和与哈希表的奥义 ​

真正的考古大师会记录每一步的线索！通过使用前缀和和哈希表，我们可以将时间复杂度优化到线性级别。

核心优化点 ​

  1. 前缀和：记录从根节点到当前节点的路径和
  2. 哈希表：存储前缀和的出现次数，快速查找是否存在满足条件的路径

关键步骤演示（以示例说明） ​

目标值：8

前缀和哈希表：{0:1} （初始化）

构建过程：
1. 根节点10，前缀和10 → 查找10-8=2，不存在
   → 更新哈希表：{0:1, 10:1}
2. 左子节点5，前缀和15 → 查找15-8=7，不存在
   → 更新哈希表：{0:1, 10:1, 15:1}
3. 左子节点3，前缀和18 → 查找18-8=10，存在（计数+1）
   → 更新哈希表：{0:1, 10:1, 15:1, 18:1}
...

Java实现 ​

java
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        // 哈希表存储前缀和
        Map<Long, Integer> prefixSumMap = new HashMap<>();
        prefixSumMap.put(0L, 1); // 初始化
        return dfs(root, 0L, targetSum, prefixSumMap);
    }

    private int dfs(TreeNode node, long currentSum, int targetSum, Map<Long, Integer> prefixSumMap) {
        if (node == null) return 0;

        currentSum += node.val; // 更新当前路径和
        int count = prefixSumMap.getOrDefault(currentSum - targetSum, 0); // 查找满足条件的路径

        // 更新哈希表
        prefixSumMap.put(currentSum, prefixSumMap.getOrDefault(currentSum, 0) + 1);

        // 递归遍历左右子树
        count += dfs(node.left, currentSum, targetSum, prefixSumMap);
        count += dfs(node.right, currentSum, targetSum, prefixSumMap);

        // 回溯，恢复哈希表状态
        prefixSumMap.put(currentSum, prefixSumMap.get(currentSum) - 1);
        return count;
    }
}

复杂度分析
时间复杂度：O(n)（只需遍历一次树）
空间复杂度：O(n)（哈希表存储）

解法对比 ​

方法时间复杂度空间复杂度优势
双重递归O(n²)O(n)实现简单
前缀和+哈希表O(n)O(n)时间效率最优

模式总结 ​

本题体现了两个关键算法思想：

  1. 前缀和：通过记录累加和，快速计算任意区间的和
  2. 哈希表优化：通过空间换时间，将查找操作优化到常数级别

这种模式可以扩展到：

  • 数组中子数组和等于目标值的问题
  • 其他需要快速计算区间和的场景

考古大师心法 ​

优秀的算法设计就像破解宝藏密码：

  1. 记录线索：通过前缀和记录每一步的路径和
  2. 快速查找：利用哈希表快速定位满足条件的路径
  3. 回溯清理：在递归返回时恢复状态，避免干扰其他路径

记住：当遇到需要频繁计算区间和或路径和的场景时，不妨先问问自己——能否通过前缀和和哈希表来优化查找效率？

作者：忍者算法
公众号：忍者算法

二叉树专题精讲已整理完毕，包含20+经典题型解析及代码模板。关注公众号回复【二叉树】获取通关秘籍～